Recovery of the sparsity pattern (or support) of an unknown sparse vectorfrom a small number of noisy linear measurements is an important problem incompressed sensing. In this paper, the high-dimensional setting is considered.It is shown that if the measurement rate and per-sample signal-to-noise ratio(SNR) are finite constants independent of the length of the vector, then theoptimal sparsity pattern estimate will have a constant fraction of errors.Lower bounds on the measurement rate needed to attain a desired fraction oferrors are given in terms of the SNR and various key parameters of the unknownvector. The tightness of the bounds in a scaling sense, as a function of theSNR and the fraction of errors, is established by comparison with existingachievable bounds. Near optimality is shown for a wide variety of practicallymotivated signal models.
展开▼
